import java.util.*;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

public class Test {
    // 题目1 ：二叉搜索树中的众数
    List<Integer> ans = new LinkedList<>();
    int base, count, maxCount;

    public int[] findMode(TreeNode root) {
        TreeNode cur = root;
        TreeNode mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                }else{
                    mostRight.right = null;
                    update(cur.val);
                    cur = cur.right;

                }
            }else{
                update(cur.val);
                cur = cur.right;
            }
        }

        int[] nums = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++){
            nums[i] = ans.get(i);
        }

        return nums;

    }

    private void update(int x){
        if(x == base){
            count++;
        }else{
            base = x;
            count = 1;
        }

        if(count == maxCount){
            ans.add(base);
        }

        if(count > maxCount){
            ans.clear();
            maxCount = count;
            ans.add(base);
        }
    }

    // 题目2：平衡二叉树
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) >= 0;
    }

    private int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = getHeight(root.left);
        if(left < 0){
            return -1;
        }

        int right = getHeight(root.right);
        if(right < 0){
            return -1;
        }

        if(Math.abs(right - left) < 2){
            return left < right ? right + 1 : left + 1;
        }else{
            return -1;
        }
    }

    // 题目3：完全二叉树的节点个数
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }

        int left = getHeight1(root.left);
        int right = getHeight1(root.right);

        if(left == right){
            return countNodes(root.right) + (1 << left);
        }else{
            return countNodes(root.left) + (1 << right);
        }

    }

    private int getHeight1(TreeNode root){
        int height = 0;
        while(root != null){
            height++;
            root = root.left;
        }
        return height;
    }

    // 题目4：不同的二叉搜索树
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                G[i] += G[i - j] * G[j - 1];
            }
        }
        return G[n];
    }

    // 题目5：不同路径
    public boolean hasPathSum(TreeNode root, int target) {
        if(root == null){
            return false;
        }

        if(root.left == null && root.right == null){
            return root.val == target;
        }

        target = target - root.val;

        return hasPathSum(root.left, target) || hasPathSum(root.right, target);
    }

    // 题目6：不同路径Ⅱ
    List<List<Integer>> lists = new LinkedList<>();
    Deque<Integer> queue = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        allPath(root, target);
        return lists;
    }

    private void allPath(TreeNode root, int target){
        if(root == null){
            return;
        }
        queue.offer(root.val);
        if(root.left == null && root.right == null && root.val == target){
            lists.add(new LinkedList<>(queue));
        }
        target = target - root.val;
        pathSum(root.left, target);
        pathSum(root.right, target);
        queue.pollLast();
    }

    // 题目7 ：合并二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null){
            return root2;
        }

        if(root2 == null){
            return root1;
        }

        TreeNode root = new TreeNode(root1.val + root2.val);

        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);

        return root;
    }

    // 题目8：二叉树的直径
    // 给你一棵二叉树的根节点，返回该树的 直径 。
    //
    //二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
    //
    //两节点之间路径的 长度 由它们之间边数表示。

    // 我的解法是，只能计算过根节点的最大直径。
    public int diameterOfBinaryTree1(TreeNode root) {
        if(root == null){
            return 0;
        }

        int left = height(root.left);
        int right = height(root.right);

        return left + right;
    }

    private int height(TreeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }

    // 官方题解：
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;
    }

    private int depth(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = depth(root.left);
        int right = depth(root.right);

        max = Math.max(left + right, max);

        return Math.max(left , right) + 1;
    }

    // 题目9：单值二叉树
    public boolean isUnivalTree(TreeNode root) {
        int base = root.val;
        return preOrder(root, base);
    }

    private boolean preOrder(TreeNode root, int base){
        if(root == null){
            return true;
        }

        if(root.val != base){
            return false;
        }
        return preOrder(root.left, base) && preOrder(root.right, base);
    }

    public boolean isUnivalTree1(TreeNode root) {
        return preOrder1(root, root.val);
    }

    private boolean preOrder1(TreeNode root, int base){
        if(root == null){
            return true;
        }

        return root.val == base &&  preOrder1(root.left, base) && preOrder1(root.right, base);
    }
}
